#ifndef JSONCPP_BATCHALLOCATOR_H_INCLUDED
# define JSONCPP_BATCHALLOCATOR_H_INCLUDED

# include <stdlib.h>
# include <assert.h>

# ifndef JSONCPP_DOC_EXCLUDE_IMPLEMENTATION

namespace Json
{

    /* Fast memory allocator.
     *
     * This memory allocator allocates memory for a batch of object (specified by
     * the page size, the number of object in each page).
     *
     * It does not allow the destruction of a single object. All the allocated objects
     * can be destroyed at once. The memory can be either released or reused for future
     * allocation.
     *
     * The in-place new operator must be used to construct the object using the pointer
     * returned by allocate.
     */
    template < typename AllocatedType
    , const unsigned int objectPerAllocation >
    class BatchAllocator
    {
    public:
        typedef AllocatedType Type;

        BatchAllocator( unsigned int objectsPerPage = 255 )
            : freeHead_( 0 )
            , objectsPerPage_( objectsPerPage )
        {
//      printf( "Size: %d => %s\n", sizeof(AllocatedType), typeid(AllocatedType).name() );
            assert( sizeof( AllocatedType ) * objectPerAllocation >= sizeof( AllocatedType * ) ); // We must be able to store a slist in the object free space.
            assert( objectsPerPage >= 16 );
            batches_ = allocateBatch( 0 );   // allocated a dummy page
            currentBatch_ = batches_;
        }

        ~BatchAllocator()
        {
            for ( BatchInfo *batch = batches_; batch; )
            {
                BatchInfo *nextBatch = batch->next_;
                free( batch );
                batch = nextBatch;
            }
        }

        /// allocate space for an array of objectPerAllocation object.
        /// @warning it is the responsability of the caller to call objects constructors.
        AllocatedType *allocate()
        {
            if ( freeHead_ ) // returns node from free list.
            {
                AllocatedType *object = freeHead_;
                freeHead_ = *( AllocatedType ** )object;
                return object;
            }

            if ( currentBatch_->used_ == currentBatch_->end_ )
            {
                currentBatch_ = currentBatch_->next_;

                while ( currentBatch_  &&  currentBatch_->used_ == currentBatch_->end_ )
                    currentBatch_ = currentBatch_->next_;

                if ( !currentBatch_ )  // no free batch found, allocate a new one
                {
                    currentBatch_ = allocateBatch( objectsPerPage_ );
                    currentBatch_->next_ = batches_; // insert at the head of the list
                    batches_ = currentBatch_;
                }
            }

            AllocatedType *allocated = currentBatch_->used_;
            currentBatch_->used_ += objectPerAllocation;
            return allocated;
        }

        /// Release the object.
        /// @warning it is the responsability of the caller to actually destruct the object.
        void release( AllocatedType *object )
        {
            assert( object != 0 );
            *( AllocatedType ** )object = freeHead_;
            freeHead_ = object;
        }

    private:
        struct BatchInfo
        {
            BatchInfo *next_;
            AllocatedType *used_;
            AllocatedType *end_;
            AllocatedType buffer_[objectPerAllocation];
        };

        // disabled copy constructor and assignement operator.
        BatchAllocator( const BatchAllocator & );
        void operator =( const BatchAllocator & );

        static BatchInfo *allocateBatch( unsigned int objectsPerPage )
        {
            const unsigned int mallocSize = sizeof( BatchInfo ) - sizeof( AllocatedType ) * objectPerAllocation
                                            + sizeof( AllocatedType ) * objectPerAllocation * objectsPerPage;
            BatchInfo *batch = static_cast<BatchInfo*>( malloc( mallocSize ) );
            batch->next_ = 0;
            batch->used_ = batch->buffer_;
            batch->end_ = batch->buffer_ + objectsPerPage;
            return batch;
        }

        BatchInfo *batches_;
        BatchInfo *currentBatch_;
        /// Head of a single linked list within the allocated space of freeed object
        AllocatedType *freeHead_;
        unsigned int objectsPerPage_;
    };


} // namespace Json

# endif // ifndef JSONCPP_DOC_INCLUDE_IMPLEMENTATION

#endif // JSONCPP_BATCHALLOCATOR_H_INCLUDED

